package com.swjd.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author 刘涛
 * @create 2021/9/28 22:34
 */
public class MergetSort {
    public static void main(String[] args) {
       /* int arr[] = {8, 4, 5, 7, 1, 3, 6, 2,};
        int temp[] = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));*/

        //测试归并排序速度  8万个数据测试
        long start = System.currentTimeMillis();
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 8000000);//生成[0,8000000)
        }
        int temp[] = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        long end = System.currentTimeMillis();
        System.out.println("运行时长：" + (end - start) + "ms");
    }

    /**
     * 分+合数组
     *
     * @param arr   原数组
     * @param left  左边初始索引
     * @param right 右边最后索引
     * @param temp  临时储存数组
     */
    public static void mergeSort(int arr[], int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;//中间索引
            //向左递归分解
            mergeSort(arr, left, mid, temp);
            //向右递归分解
            mergeSort(arr, mid + 1, right, temp);
            //上一句执行到这一条，代表已经分解递归完毕了，然后再开始整合  合并
            merge(arr, left, right, mid, temp);
        }
    }

    /**
     * 合并数组
     *
     * @param arr   排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param right 右边最后索引
     * @param mid   中间索引
     * @param temp  临时存储数组
     */
    public static void merge(int arr[], int left, int right, int mid, int[] temp) {
        int l = left;//左边有序序列初始索引
        int r = mid + 1;//右边有序序列的初始索引 计算方式：数组中间索引的下一个就是右边索引
        int t = 0;//temp索引
        //先把左右两边数据(有序)按规则填充到临时数组，直到有一边全部处理完毕为止
        //当左指针还没到中间并且右指针还没有到最后 即两边都没有扫描完
        while (l <= mid && r <= right) {
            //如果左边当前数小于或者等于右边当前数
            if (arr[l] <= arr[r]) {
                //将左边的(较小的)的放入临时数组
                temp[t] = arr[l];
                t++;//放入之后临时数组索引应该往后移
                l++;//左边数据放入之后应该把索引往后移
            } else if (arr[r] <= arr[l]) {
                temp[t] = arr[r];
                t++;
                r++;
            }
        }

        //把剩余未处理完的一边，直接按顺序填充到临时数组
        //左边还有剩余元素
        while (l <= mid) {
            temp[t] = arr[l];
            t++;
            l++;
        }
        while (r <= right) {
            temp[t] = arr[r];
            t++;
            r++;
        }

        //将temp数组有数据的覆盖填充进arr
        t = 0;//指向临时数组第一个位置
        int le = left;//临时指针，指向原数组第一个位置
        //数组左指针要不超过数组最后的，才算是有空间能往里填充
        while (le <= right) {
            arr[le] = temp[t];
            t++;
            le++;
        }
    }
}
